# coding: utf-8
# 邻接矩阵实现(非常直白)
# 图的几个经典问题：1.寻找路径（包括最短路径） 2.寻找连通分量（包括有向图强连通分量） 3.判断有向图是否有环
# 图算法领域10大经典算法 https://www.cnblogs.com/v-July-v/archive/2011/02/14/1983678.html

import networkx as nx
import matplotlib.pyplot as plt

class GraphMat(object):
    def __init__(self, num_vertex):
        if num_vertex>26:
            raise Exception('不能超过26个节点')
        self.mat = [[0]*num_vertex for _ in range(num_vertex)]
        self.num_vertex=num_vertex
        
    def addEdge(self, fromNode, toNode, weight=1):
        self.mat[fromNode][toNode]=weight
        return self
    
    #完美绘制有向、加权图
    def draw(self, directed=True):
        if directed:
            G=nx.DiGraph()
        else:
            G=nx.Graph()
        G.add_nodes_from(range(self.num_vertex))
        
        edges=[]
        for v1 in range(self.num_vertex):
            for v2 in range(self.num_vertex):
                if self.mat[v1][v2]>0:
                    edges.append((v1,v2,self.mat[v1][v2]))
        G.add_weighted_edges_from(edges)
        
        pos=nx.spring_layout(G)
        edgeLabels = nx.get_edge_attributes(G,'weight')
        nodeLabels={i:chr(i+ord('a')) for i in range(self.num_vertex)}
        nx.draw_networkx(G, pos=pos,with_labels=True, node_color='y',labels=nodeLabels)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edgeLabels)
        
    # TODO 迪克斯特拉算法
    def shortestPath(self):
        pass
        
gm=GraphMat(6)
a,b,c,d,e,f=range(6)
gm.addEdge(a,b,4).addEdge(a,c,2)
gm.addEdge(b,c,1).addEdge(b,d,5)
gm.addEdge(c,d,8).addEdge(c,e,10)
gm.addEdge(d,e,2).addEdge(d,f,6)
gm.addEdge(e,f,3)
gm.draw(False)

